package backMind

// 背包问题升级版
// 在背包承重和物品总重最大前提下，引入物品价值变量
// 对于一组不同重量，不同价值，不可分割的物品，如何选择哪些物品放入背包
// 在满足背包最大重量限制前提下，背包中可装入物品的总价值最大是多少呢

// BackPackValue i当前决策哪个物品, cw当前物品总重，cv当前物品总价值，n物品个数,w背包最大承重
// weights 物品重量列表，values 对应物品价值列表， maxV物品最大价值
func BackPackValue(i, cw, cv, n, w int, weights, values []int, maxV *int) {
	// 判断结束条件
	if cw == w || i == n {
		// 记录最大总价值
		if cv > *maxV {
			*maxV = cv
		}
		return
	}

	// 选择第i个物品不放入背包
	BackPackValue(i+1, cw, cv, n, w, weights, values, maxV)

	// 如果当前物品放入背包满足条件
	if cw+weights[i] <= w {
		// 选择第i个物品放入背包
		cw += weights[i]
		cv += values[i]
		BackPackValue(i+1, cw, cv, n, w, weights, values, maxV)
	}
}
